package algorithm.dynamicProgramming.leetcode;
//70. 爬楼梯
public class ClimbStairs {


    public static void main(String[] args) {
        System.out.println(climbStairs2(4));
    }
    public static int climbStairs(int n) {
        if (n==1 ){
            return n;
        }
        int[] f = new int[n+1];
        f[0]=0;
        f[1] =1;
        f[2] = 2;
        for (int i =3;i<=n;i++){
           f[i] = f[i-1]+f[i-2];
        }

        return f[n];

    }

    //双指针
    public static int climbStairs2(int n) {
        if (n==1 ){
            return n;
        }
        int p=0,q=0, r=1;
        for (int i = 0; i < n; i++) {
            p =q;
            q=r;
            r = p+q;
        }
        return r;
    }
}
